#include <iostream>
#include <string>
#include <vector>
#include <climits>
#include "BinaryTree.h"
using namespace std;

// 98.23 %
class Solution1
{
  public:
	bool isValidBST(TreeNode *root)
	{
		if (!root)
			return true;
		bool rel = checkl(root->left, root->val), rer = checkr(root->right, root->val);
		if (root->right)
			rer = checkr(root->right, root->val);
		return rel && rer && isValidBST(root->left) && isValidBST(root->right);
	}
	bool checkl(TreeNode *root, int value)
	{
		if (!root)
			return true;
		return root->val < value && checkl(root->left, value) && checkl(root->right, value);
	}
	bool checkr(TreeNode *root, int value)
	{
		if (!root)
			return true;
		return root->val > value && checkr(root->left, value) && checkr(root->right, value);
	}
};

class Solution
{
  public:
	bool isValidBST(TreeNode *root)
	{
		return isValidBST(root, LONG_MIN, LONG_MAX);
	}
	bool isValidBST(TreeNode *root, long m_min, long m_max)
	{
		if (root == NULL)
			return true;
		if (root->val <= m_min || root->val >= m_max)
			return false;
		return isValidBST(root->left, m_min, root->val) && isValidBST(root->right, root->val, m_max);
	}
};

int main()
{
	int arr[] = {5, 1, 0, 0, 4, 3, 0, 0, 6, 0, 0};
	int n = sizeof(arr) / sizeof(arr[0]);
	TreeNode *tree = createBinaryTree(arr, n);
	int sum = 8;
	preorderPrint(tree);
	cout << endl;
	cout << Solution().isValidBST(tree) << endl;
	deleteBinaryTree(tree);
	return 0;
}
